1. Field of Invention
The present invention relates generally to methods and apparatus for implementing multiple return points for a call to a function. More particularly, the present invention relates to method and apparatus for efficiently enabling addresses for multiple return points to be obtained.
2. Description of the Relevant Art
Computer systems are often linked across a network, e.g., local area networks, intranets, and internets, of computer systems such that they may share resources such as software, or program, code. Further, many programs, which include routines, are written such that a program calls xe2x80x9cexternalxe2x80x9d functions which may not be included within the program. In general, the functions may be shared by many routines, thereby allowing computer system resources to be used more efficiently.
When a routine is arranged to call functions, the functions that are called must eventually return into the routine. Further, the returns to the routine must be made to the appropriate locations within the routine. With reference to FIG. 1, the flow between a computer program and functions called by the program will be described. Computer code 104 includes a routine g( ) 108. Routine g( ) 108 includes instructions which are executed. As shown, the instructions include repeated calls 112 to a function f( ) 116.
When function f( ) 116 is called and executes xe2x80x9cnormally,xe2x80x9d e.g., no exception is thrown, then function f( ) 116 typically completes execution, and a return is made to routine g( ) 108a computer routine. The location within routine g( ) 108a computer routine to which function f( ) 116 returns is dependent upon the call site, or the site within routine g( ) 108a computer routine which called function f( ) 116. Specifically, if function f( ) 116 executes as a result of call 112a, then function f( ) 116 returns to return address 120 which, as will be appreciated by those skilled in the art, is located immediately after call 112a within routine g( ) 108a computer routine. Similarly, if function f( ) 116 executes when called by call 112b, then function f( ) 116 returns to return address 124. Once function f( ) 116 returns to routine g( ) 108a computer routine, routine g( ) 108a generally continues to execute.
Many functions may have more than one return site, or point. By way of example, a function may have a normal, or expected, return point as well as an alternate return point. Alternate return points are often considered to be xe2x80x9cabnormalxe2x80x9d return points such as return points associated with thrown exceptions. The alternate return points are typically stored, or cataloged, within an overall program such that the return points may be readily identified as needed. By way of example, alternate return points may be needed by a program during the processing of an exception thrown by a function which does not handle exceptions.
One mechanism used to associate functions with alternate return points is a return point, or return address, table. FIG. 2a is a diagrammatic representation of a return point table associated with a call stack. A call stack 204 includes a caller frame 208 which calls another frame, i.e., callee frame 212. Callee 212 is associated with a function f( ) 214. As such, when caller 208 calls callee 212, function f( ) 214 begins to execute.
At the end of the execution of function f( ) 214 , function f( ) 214 and, hence, callee 212 returns to caller 208. When the return to caller 208 is not a normal return, then the normal return address may be used as an index 216 into a return point table 220 to identify the proper alternative return point. For example, if the normal return address is xe2x80x9c1234xe2x80x9d, then return point table 220 may be searched to find xe2x80x9c1234.xe2x80x9d Once xe2x80x9c1234xe2x80x9d is found, then the alternate return point address associated with xe2x80x9c1234xe2x80x9d may be obtained. As shown, for a normal return address of xe2x80x9c1234,xe2x80x9d the corresponding alternate return point address is xe2x80x9c1256.xe2x80x9d Once obtained, the alternate return point address may then be used to ensure that callee 212 returns to caller 208 appropriately.
Although the use of a return point table, which is generally a look-up table or a hash table, is effective to identify a proper return point for a callee, the implementation of a table look-up is often slow. A faster process for implementing multiple return points involves eliminating table look-ups to identify return points. As will be appreciated by those skilled in the art, during the execution of a function, it is essentially xe2x80x9cknownxe2x80x9d to the function whether the function should return using a normal return, or whether the function should return using an alternate return. Therefore, data pertaining to the alternate return address is available to be stored.
FIG. 2b is a diagrammatic representation of a routine which is arranged to store alternate return address data. A routine g( ) 236 includes a call 238 to a function f( ). Regardless of whether call 238 to a function f( ) results in the need to return to an alternate address, call 238 would normally return to return address 240. Return address 240 identifies stored alternate return address data 242. The stored alternate return address data 242 is located within routine g( ) 236, a computer routine near call 238 to enable alternate return address data 242 to be readily accessed. In general, alternate return address data 242 is stored in the instruction stream itself. Since stored alternate return address data 242 may not represent a legal instruction, or may have undesirable side effects such as overwriting a value in a register or a memory cell, execution of routine g( ) may not continue at address 240 but must instead continue at next instruction 244.
When call 238 returns normally, call 238 should return to next instruction 244. As shown, within routine g( ) 236, next instruction 244 is offset from stored alternate return address data 242 by a distance D. Therefore, when call 238 returns normally, call 238 must return to a location that is specified by the location of return address 240 incremented by offset D, i.e., the location of next instruction 244. Typically, as distance D has a value of four bytes, next instruction 244 is offset from the location of return address 240 by four bytes.
While accessing a stored alternate return address in a program is more time-efficient than implementing a table look-up when an alternate return address is needed, when an alternate return address is not needed, the ability to access a stored alternate return address often adversely affects the performance of the program. Adding an offset to the location of a return address in order to locate a subsequent instruction to be executed when a function call returns normally is often relatively slow, and may incur a performance penalty associated with computing the location of the subsequent instruction. In other words, the speed associated with a normal return may be compromised by the implementation of stored alternate return addresses. Further, branch prediction which is often used to generate a xe2x80x9cbest-guessxe2x80x9d estimate for a normal return, or a return which is most likely to occur, may be compromised by the use of jumps, as will be appreciated by those skilled in the art.
Alternatively, xe2x80x9cjumpsxe2x80x9d may be used to bypass the stored alternate address, as follows. Jumps, or branches, are often included in programs, or routines, to bypass sections of code which may be unnecessary in some situations. For example, jumps may be implemented in a routine to enable a stored alternate return address to be bypassed when a function call returns normally, as shown in FIG. 2c. Within routine g( ) 266, a call 268 is made to a function f( ). When call 268 returns normally, the return is made to the location in routine g( ) 266 specified by a return address 270. The location corresponding to return address 270 is an instruction 272 to jump to a location L which is located at a fixed offset F from instruction 272. Therefore, when call 268 returns normally to return address 270, a jump is made to next instruction 274. Such a jump bypasses, or branches around, stored alternate return address data 276.
While the implementation of jumps may reduce performance penalties, e.g., hardware performance penalties, associated with adding an offset to a return address in order to find the location of a subsequent instruction, jumps may be slow. Additional code must be included in a program to allow for jumps, thereby increasing the overall size of the program.
As discussed above, conventional methods for implementing multiple return points for function calls are often slow and inefficient, and, hence, the implementation of multiple return points may adversely affect the performance of programs associated with the function calls. Therefore, what is desired is an efficient method and apparatus for implementing multiple return points such that both normal returns and alternate returns occur efficiently.
Methods and apparatus for efficiently enabling an alternate return address associated with a function call to essentially be cached such that the alternate return address may be readily accessed are disclosed. According to one aspect of the present invention, a method for enabling a return address associated with a function called by a routine to be efficiently cached includes calling the function from within the routine while the routine is executing. In general, the function is external to the routine. The function, once called, begins executing. Eventually, the function returns to the routine. Specifically, the function returns to a location in the routine that is identified by an expected return point, or normal return address. The instruction in the routine that corresponds to the expected return point is a xe2x80x9cdummyxe2x80x9d instruction that executes with a low computational overhead. The dummy instruction is selected to execute without affecting the normal program execution, i.e., its result is not used. Instead, the purpose of the dummy instruction is to encode the alternate return point, or points, in a suitable way.
In one embodiment, when the function returns to the routine in an expected manner, the execution of the function is completed prior to returning to the expected return point, and the execution of the dummy instruction has no effect. In another embodiment, when the function does return to the alternate return point, code is executed to access the dummy instruction stored at the normal return point, and the address of the alternate return point is computed from the library value that the dummy instruction represents.
These and other advantages of the present invention will become apparent upon reading the following detailed descriptions and studying the various figures of the drawings.